
Partial Orders
Definition
A partial order (S, ⊑) is a set S equipped with a binary relation ⊑ that is:
•
Reflexive: ∀x ∈ S, x ⊑ x
•
Transitive: ∀x, y, z ∈ S, x ⊑ y ∧ y ⊑ z ⇒ x ⊑ z
•
Antisymmetric: ∀x, y ∈ S, x ⊑ y ∧ y ⊑ x ⇒ x = y
•
y ∈ S is an upper bound for X (X ⊑ y) if ∀x ∈ X , x ⊑ y
•
y ∈ S is the least upper bound for X (X
F
y) if y is an upper bound for X and
∀z ∈ S, X ⊑ z ⇒ y ⊑ z
•
y ∈ S is a lower bound for X (y ⊑ X ) if ∀x ∈ X , y ⊑ x
•
y ∈ S is the greatest lower bound for X (y
F
X ) if y is a lower bound for X and
∀z ∈ S, z ⊑ X ⇒ z ⊑ y
Lattices and Fixed Points 6 / 31